<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="utf-8" />
   
  <meta name="keywords" content="Java Python" />
   
  <meta name="description" content="From Zero to Hero" />
  
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <title>
    队列和栈-合集 |  朱酱酱的学习博客
  </title>
  <meta name="generator" content="hexo-theme-yilia-plus">
  
  <link rel="shortcut icon" href="/favicon.ico" />
  
  
<link rel="stylesheet" href="/css/style.css">

  
<script src="/js/pace.min.js"></script>


  

  

<link rel="alternate" href="/atom.xml" title="朱酱酱的学习博客" type="application/atom+xml">
</head>

</html>

<body>
  <div id="app">
    <main class="content">
      <section class="outer">
  <article id="post-LeetcodeExplore/队列和栈-合集" class="article article-type-post" itemscope
  itemprop="blogPost" data-scroll-reveal>

  <div class="article-inner">
    
    <header class="article-header">
       
<h1 class="article-title sea-center" style="border-left:0" itemprop="name">
  队列和栈-合集
</h1>
  

    </header>
    

    
    <div class="article-meta">
      <a href="/2020/07/20/LeetcodeExplore/%E9%98%9F%E5%88%97%E5%92%8C%E6%A0%88-%E5%90%88%E9%9B%86/" class="article-date">
  <time datetime="2020-07-20T07:52:53.000Z" itemprop="datePublished">2020-07-20</time>
</a>
      
      
      
<div class="word_count">
    <span class="post-time">
        <span class="post-meta-item-icon">
            <i class="ri-quill-pen-line"></i>
            <span class="post-meta-item-text"> 字数统计:</span>
            <span class="post-count">7k字</span>
        </span>
    </span>

    <span class="post-time">
        &nbsp; | &nbsp;
        <span class="post-meta-item-icon">
            <i class="ri-book-open-line"></i>
            <span class="post-meta-item-text"> 阅读时长≈</span>
            <span class="post-count">30分钟</span>
        </span>
    </span>
</div>

      
    </div>
    

    
    
    <div class="tocbot"></div>





    

    <div class="article-entry" itemprop="articleBody">
      


      

      
      <h1 id="队列和栈-合集"><a href="#队列和栈-合集" class="headerlink" title="队列和栈-合集"></a>队列和栈-合集</h1><p>（本系列是针对Leetcode上常见的队列和栈进行总结。）</p>
<a id="more"></a>



<h1 id="1-基础知识"><a href="#1-基础知识" class="headerlink" title="1. 基础知识"></a>1. 基础知识</h1><ul>
<li><p>在数组中，我们可以通过<strong>索引</strong>随机访问元素。但是，在某些情况下，我们可以想要限制处理的顺序。</p>
</li>
<li><p>这两种不同的顺序就是 ， <code>先入先出</code> <code>先入后出</code> 。以及两个相应的线性数据结构，<strong>队列和栈</strong></p>
</li>
<li><p>在做到算法题的时候，<strong>队列一般用于BFS，而系统栈用于DFS</strong></p>
</li>
</ul>
<h2 id="1-1-队列（先入先出）"><a href="#1-1-队列（先入先出）" class="headerlink" title="1.1 队列（先入先出）"></a>1.1 队列（先入先出）</h2><p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200720/134217670.png" alt="mark"></p>
<!--more-->

<ul>
<li>在FIFO 数据结构中，将首先处理添加到队列的第一个元素。</li>
<li>如上图所示，队列是典型的FIFO的数据结构。<strong>插入</strong>(insert) 操作也称为入队（enqueue），<strong>新元素始终被添加到队列的末尾</strong>。<strong>删除</strong>（delete） 操作也被称为出队(dequeue) 。 你<strong>只能移除第一个元素</strong>。</li>
<li><strong>总结：队尾入队，队首出队。</strong></li>
</ul>
<p><strong>出队：</strong><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200720/135940985.jpg" alt="mark"></p>
<p>*<em>入队 : *</em><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200720/140053661.png" alt="mark"></p>
<h3 id="1-1-1-数组实现队列"><a href="#1-1-1-数组实现队列" class="headerlink" title="1.1.1 数组实现队列"></a>1.1.1 数组实现队列</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 数组实现队列</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MyQueue</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 1. 数组存放元素</span></span><br><span class="line">    <span class="keyword">private</span> List&lt;Integer&gt; data;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 2. 指向开始位置的指针</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> p_start;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 3. 构造函数</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyQueue</span><span class="params">()</span></span>&#123;</span><br><span class="line">        data = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">        p_start = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 4. 入队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">enQueue</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">        data.add(x);</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 5. 出队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">deQueue</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty() == <span class="keyword">true</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 出队相当于开始索引后移</span></span><br><span class="line">        p_start ++;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 6. 获取队首元素</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getFront</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> data.get(p_start);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 7. 判断队列是否为空</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> p_start &gt;= data.size();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"> <span class="class"><span class="keyword">class</span> <span class="title">Main</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        MyQueue q = <span class="keyword">new</span> MyQueue();</span><br><span class="line">        q.enQueue(<span class="number">5</span>);</span><br><span class="line">        q.enQueue(<span class="number">3</span>);</span><br><span class="line">        <span class="keyword">if</span> (q.isEmpty() == <span class="keyword">false</span>) &#123;</span><br><span class="line">            System.out.println(q.getFront());</span><br><span class="line">        &#125;</span><br><span class="line">        q.deQueue();</span><br><span class="line">        <span class="keyword">if</span> (q.isEmpty() == <span class="keyword">false</span>) &#123;</span><br><span class="line">            System.out.println(q.getFront());</span><br><span class="line">        &#125;</span><br><span class="line">        q.deQueue();</span><br><span class="line">        <span class="keyword">if</span> (q.isEmpty() == <span class="keyword">false</span>) &#123;</span><br><span class="line">            System.out.println(q.getFront());</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>缺点：</strong></p>
<ul>
<li>上面的实现很简单，但在某些情况下效率很低。 随着起始指针的移动，浪费了越来越多的空间。 当我们有空间限制时，这将是难以接受的。</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200720/145353792.png" alt="mark"></p>
<ul>
<li>让我们考虑一种情况，即我们只能分配一个最大长度为 5 的数组。当我们只添加少于 5 个元素时，我们的解决方案很有效。 例如，如果我们只调用入队函数四次后还想要将元素 10 入队，那么我们可以成功。</li>
<li>但是我们不能接受更多的入队请求，这是合理的，因为现在队列已经满了。但是如果我们将一个元素出队呢？</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200720/145423708.png" alt="mark"></p>
<h3 id="1-1-2-剑指-Offer-09-用两个栈实现队列"><a href="#1-1-2-剑指-Offer-09-用两个栈实现队列" class="headerlink" title="1.1.2 剑指 Offer 09. 用两个栈实现队列"></a>1.1.2 <a href="https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/" target="_blank" rel="noopener">剑指 Offer 09. 用两个栈实现队列</a></h3><p><strong>题目描述：</strong></p>
<p>用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 <code>appendTail</code> 和 <code>deleteHead</code> ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">示例 1：</span><br><span class="line"></span><br><span class="line">输入：</span><br><span class="line">[&quot;CQueue&quot;,&quot;appendTail&quot;,&quot;deleteHead&quot;,&quot;deleteHead&quot;]</span><br><span class="line">[[],[3],[],[]]</span><br><span class="line">输出：[null,null,3,-1]</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">示例 2：</span><br><span class="line"></span><br><span class="line">输入：</span><br><span class="line">[&quot;CQueue&quot;,&quot;deleteHead&quot;,&quot;appendTail&quot;,&quot;appendTail&quot;,&quot;deleteHead&quot;,&quot;deleteHead&quot;]</span><br><span class="line">[[],[],[5],[2],[],[]]</span><br><span class="line">输出：[null,-1,null,null,5,2]</span><br></pre></td></tr></table></figure>



<p><strong>遇到的问题</strong></p>
<ul>
<li><strong>栈无法实现队列的功能：</strong>栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈</li>
<li><strong>双栈可以实现列表的倒序</strong>：</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">设有含三个元素的栈 </span><br><span class="line">A &#x3D; [1,2,3] 和空栈 B &#x3D; []。</span><br><span class="line">若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A &#x3D; [] , B &#x3D; [3,2,1]，即 栈 B 元素实现栈 A 元素倒序 。</span><br></pre></td></tr></table></figure>

<ul>
<li><strong>利用栈B删除队首元素：倒序后，B执行出栈就相当于删除了A的栈底元素，即对应队首元素</strong></li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200630/141348516.png" alt="mark"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">CQueue</span> </span>&#123;</span><br><span class="line">    LinkedList&lt;Integer&gt; A,B;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">CQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        A = <span class="keyword">new</span> LinkedList&lt;Integer&gt;();</span><br><span class="line">        B = <span class="keyword">new</span> LinkedList&lt;Integer&gt;();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">appendTail</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        A.add(value);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">deleteHead</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 1. B不为空，说明已经完成了倒叙，直接返回B栈顶元素即可</span></span><br><span class="line">        <span class="keyword">if</span> (!B.isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> B.poll();</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (A.isEmpty())&#123;</span><br><span class="line">            <span class="comment">// 2. 如果A为空,说明两个栈都为空</span></span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 3. 说明两个栈都存在元素</span></span><br><span class="line">            <span class="keyword">while</span> (!A.isEmpty())&#123;</span><br><span class="line">                B.add(A.remove());</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> B.remove();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>具体的解析：在我的Leetcode专题里面有，所以这里不再过度阐述。</strong></p>
<h3 id="1-1-3-622-设计循环队列"><a href="#1-1-3-622-设计循环队列" class="headerlink" title="1.1.3 622. 设计循环队列"></a>1.1.3 <a href="https://leetcode-cn.com/problems/design-circular-queue/" target="_blank" rel="noopener">622. 设计循环队列</a></h3><ul>
<li>此前，我们提供了一种简单但低效的队列实现。（数组实现）</li>
<li>更有效的方法是使用循环队列，具体来说，我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。目的是重复使用被浪费的存储空间。</li>
</ul>
<p><strong>题目描述：</strong></p>
<ul>
<li><p>设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。</p>
</li>
<li><p>循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。</p>
</li>
<li><p>你的实现应该支持如下操作：</p>
</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">MyCircularQueue(k): 构造器，设置队列长度为 k 。</span><br><span class="line">Front: 从队首获取元素。如果队列为空，返回 -1 。</span><br><span class="line">Rear: 获取队尾元素。如果队列为空，返回 -1 。</span><br><span class="line">enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。</span><br><span class="line">deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。</span><br><span class="line">isEmpty(): 检查循环队列是否为空。</span><br><span class="line">isFull(): 检查循环队列是否已满。</span><br></pre></td></tr></table></figure>



<p><strong>算法思路</strong></p>
<ul>
<li>这道题说“循环”的意思是要求我们在数组里实现。</li>
<li>在数组的操作中，我们参考“动态数组”的实现来完成。主要是为了让每一步操作的复杂度都降到最低。只不过我们自己实现动态扩容和缩容</li>
</ul>
<p>注意：</p>
<ol>
<li><p>定义循环变量 <code>front</code> 和 <code>rear</code> 。一直保持这个定义，到底是先赋值还是先移动指针就很容易想清楚了。</p>
<ul>
<li><code>front</code> 队列头部第一个有效的位置</li>
<li><code>rear</code>：指向队列尾部（即最后 1 个有效数据）的下一个位置，即下一个从队尾入队元素的位置。</li>
</ul>
</li>
<li><p><strong>为了避免“队列为空”和“队列为满”的判别条件冲突，我们有意浪费了一个位置。</strong></p>
<ul>
<li>浪费一个位置是指：循环数组中任何时刻一定至少有一个位置不存放元素。</li>
<li>判断队列为空的条件 <code>front == rear</code></li>
<li>判断队列为满的条件 <code>front == (rear + 1) % capacity</code> (可以这样理解，当 <code>rear</code> 循环到数组的前面，要从后面追上 <code>front</code>，还差一格的时候，判定队列为满。)</li>
</ul>
</li>
<li><p>因为有循环的出现，要<strong>特别注意处理数组下标可能越界的情况</strong>。指针后移的时候，索引 + 1，并且要注意取模。</p>
</li>
</ol>
<p><strong>代码实现</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//leetcode submit region begin(Prohibit modification and deletion)</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyCircularQueue</span> </span>&#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> front;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> rear;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> capacity;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] arr;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Initialize your data structure here. Set the size of the queue to be k. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyCircularQueue</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 浪费一个位置</span></span><br><span class="line">        capacity = k + <span class="number">1</span>;</span><br><span class="line">        arr = <span class="keyword">new</span> <span class="keyword">int</span>[capacity];</span><br><span class="line"></span><br><span class="line">        front = <span class="number">0</span>; <span class="comment">// 删除元素的时候，只索引 +1（注意取模）</span></span><br><span class="line">        rear  = <span class="number">0</span>; <span class="comment">// 插入元素的时候，先赋值，后索引 +1（注意取模）</span></span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Insert an element into the circular queue. Return true if the operation is successful. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">enQueue</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isFull())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 先赋值，然后索引 + 1</span></span><br><span class="line">        arr[rear] = value;</span><br><span class="line">        rear = (rear + <span class="number">1</span>) % capacity;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Delete an element from the circular queue. Return true if the operation is successful. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">deQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 先索引 + 1即可</span></span><br><span class="line">        front = (front + <span class="number">1</span>) % capacity;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Get the front item from the queue. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">Front</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr[front];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Get the last item from the queue. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">Rear</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span>  -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr[(rear - <span class="number">1</span> + capacity) % capacity];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Checks whether the circular queue is empty or not. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> rear == front;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Checks whether the circular queue is full or not. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isFull</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 经典设计</span></span><br><span class="line">        <span class="keyword">return</span> (rear + <span class="number">1</span>) % capacity == front;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h3 id="1-1-4-641-设计循环双端队列"><a href="#1-1-4-641-设计循环双端队列" class="headerlink" title="1.1.4 641. 设计循环双端队列"></a>1.1.4 <a href="https://leetcode-cn.com/problems/design-circular-deque/" target="_blank" rel="noopener">641. 设计循环双端队列</a></h3><p><strong>代码实现</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//leetcode submit region begin(Prohibit modification and deletion)</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyCircularDeque</span> </span>&#123;</span><br><span class="line">    <span class="comment">// front == rear 队列为空</span></span><br><span class="line">    <span class="comment">// (rear + 1) == front 队列为满</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> front;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> rear;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] arr;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> capacity;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Initialize your data structure here. Set the size of the deque to be k. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyCircularDeque</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">        capacity = k + <span class="number">1</span>;</span><br><span class="line">        arr = <span class="keyword">new</span> <span class="keyword">int</span>[capacity];</span><br><span class="line"></span><br><span class="line">        front = <span class="number">0</span>;</span><br><span class="line">        rear = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Adds an item at the front of Deque. Return true if the operation is successful. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">insertFront</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(isFull()) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 索引 + 1 然后赋值</span></span><br><span class="line">        front = (front - <span class="number">1</span> + capacity) % capacity;</span><br><span class="line">        arr[front] = value;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Adds an item at the rear of Deque. Return true if the operation is successful. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">insertLast</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isFull())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        arr[rear] = value;</span><br><span class="line">        rear = (rear + <span class="number">1</span>) % capacity;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Deletes an item from the front of Deque. Return true if the operation is successful. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">deleteFront</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// front 是在数组的开头，同时防止数组越界</span></span><br><span class="line">        front = (front + <span class="number">1</span>) % capacity;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Deletes an item from the rear of Deque. Return true if the operation is successful. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">deleteLast</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        rear = (rear - <span class="number">1</span> + capacity) % capacity;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Get the front item from the deque. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getFront</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr[front];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Get the last item from the deque. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getRear</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 当 rear 为0的时候防止数组越界</span></span><br><span class="line">        <span class="comment">// 因为真正的最后有效的元素是 rear - 1</span></span><br><span class="line">        <span class="keyword">return</span> arr[(rear - <span class="number">1</span> + capacity) % capacity];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Checks whether the circular deque is empty or not. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> front == rear;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Checks whether the circular deque is full or not. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isFull</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 经典设计</span></span><br><span class="line">        <span class="keyword">return</span> (rear + <span class="number">1</span>) % capacity == front;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="2-1-栈（后入先出）"><a href="#2-1-栈（后入先出）" class="headerlink" title="2.1 栈（后入先出）"></a>2.1 栈（后入先出）</h2><p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200724-160713163.png" alt="mark"></p>
<ul>
<li>在 LIFO 数据结构中，将<code>首先处理添加到队列</code>中的<code>最新元素</code>。</li>
<li>与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 <code>push</code> 。与队列类似，总是<code>在堆栈的末尾添加一个新元素</code>。但是，删除操作，退栈 <code>pop</code> ，将始终<code>删除</code>队列中相对于它的<code>最后一个元素</code>。</li>
</ul>
<h3 id="2-1-1-栈的实现"><a href="#2-1-1-栈的实现" class="headerlink" title="2.1.1 栈的实现"></a>2.1.1 栈的实现</h3><ul>
<li>栈的实现比队列容易。<code>动态数组</code>足以实现堆栈结构。这里我们提供了一个简单的实现供你参考：</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MyStack</span> </span>&#123;</span><br><span class="line">    <span class="keyword">private</span> List&lt;Integer&gt; list;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        list = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">        list.add(x);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> list.isEmpty();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 拿到栈顶元素</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">top</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> list.get(list.size() - <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">pop</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        list.remove(list.size() - <span class="number">1</span>);</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h3 id="2-1-2-155-最小栈"><a href="#2-1-2-155-最小栈" class="headerlink" title="2.1.2  155. 最小栈"></a>2.1.2  <a href="https://leetcode-cn.com/problems/min-stack/" target="_blank" rel="noopener">155. 最小栈</a></h3><p>题目描述：</p>
<p>设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">push(x) ——   将元素 x 推入栈中。</span><br><span class="line">pop() ——     删除栈顶的元素。</span><br><span class="line">top() ——     获取栈顶元素。</span><br><span class="line">getMin() —— 检索栈中的最小元素。</span><br></pre></td></tr></table></figure>



<p>示例：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">输入：</span><br><span class="line">[<span class="string">"MinStack"</span>,<span class="string">"push"</span>,<span class="string">"push"</span>,<span class="string">"push"</span>,<span class="string">"getMin"</span>,<span class="string">"pop"</span>,<span class="string">"top"</span>,<span class="string">"getMin"</span>]</span><br><span class="line">[[],[-<span class="number">2</span>],[<span class="number">0</span>],[-<span class="number">3</span>],[],[],[],[]]</span><br><span class="line"></span><br><span class="line">输出：</span><br><span class="line">[<span class="keyword">null</span>,<span class="keyword">null</span>,<span class="keyword">null</span>,<span class="keyword">null</span>,-<span class="number">3</span>,<span class="keyword">null</span>,<span class="number">0</span>,-<span class="number">2</span>]</span><br><span class="line"></span><br><span class="line">解释：</span><br><span class="line">MinStack minStack = <span class="keyword">new</span> MinStack();</span><br><span class="line">minStack.push(-<span class="number">2</span>);</span><br><span class="line">minStack.push(<span class="number">0</span>);</span><br><span class="line">minStack.push(-<span class="number">3</span>);</span><br><span class="line">minStack.getMin();   --&gt; 返回 -<span class="number">3</span>.</span><br><span class="line">minStack.pop();</span><br><span class="line">minStack.top();      --&gt; 返回 <span class="number">0</span>.</span><br><span class="line">minStack.getMin();   --&gt; 返回 -<span class="number">2</span>.</span><br></pre></td></tr></table></figure>



<p><strong>Solution：辅助栈和数据栈同步</strong></p>
<ul>
<li>特点：编写简单，不需要考虑一些边界情况（缺点：可能会存储一些多余的元素）</li>
<li>规则如下：<ul>
<li><strong>辅助栈为空的时候，必须放进来新的数字</strong></li>
<li>新来的数小于等于辅助栈栈顶元素的时候，才放入（<strong>这里“等于要考虑进去”，因为出栈的时候，相等的并且是最小值的元素要同步出栈</strong>），要不然就放入辅助栈栈顶自己</li>
<li><strong>出栈的时候，辅助栈的栈顶元素要等于数据栈栈顶的元素才出栈</strong></li>
</ul>
</li>
</ul>
<p><strong>总结：</strong></p>
<ul>
<li><strong>出栈的时候，最小值出栈才同步</strong></li>
<li><strong>入栈的时候，最小值入栈才同步</strong></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MinStack</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 数据栈</span></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; data;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 辅助栈</span></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; helper;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * initialize your data structure here.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MinStack</span><span class="params">()</span></span>&#123;</span><br><span class="line">        data =   <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        helper = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 思路1：数据栈和辅助栈在任何时候都要同步</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">        data.add(x);</span><br><span class="line">        <span class="keyword">if</span> (helper.isEmpty() || helper.peek() &gt;= x)&#123;</span><br><span class="line">            helper.add(x);</span><br><span class="line">        &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">            helper.add(helper.peek());</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="comment">// 两个栈都需要pop操作</span></span><br><span class="line">        <span class="keyword">if</span> (!data.isEmpty())&#123;</span><br><span class="line">            helper.pop();</span><br><span class="line">            data.pop();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 返回数据栈的栈顶</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">top</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!data.isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> data.peek();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">"栈元素为空"</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 返回最小栈的栈顶元素</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getMin</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!helper.isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> helper.peek();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">"栈元素为空"</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>复杂度分析：</strong></p>
<ul>
<li><strong>时间复杂度</strong>：O(1) 栈的操作</li>
<li><strong>空间复杂度</strong>：O(n) 需要一个辅助栈的空间</li>
</ul>
<h3 id="2-1-3-20-有效的括号"><a href="#2-1-3-20-有效的括号" class="headerlink" title="2.1.3 20. 有效的括号"></a>2.1.3 <a href="https://leetcode-cn.com/problems/valid-parentheses/" target="_blank" rel="noopener">20. 有效的括号</a></h3><p><strong>题目描述</strong></p>
<p>给定一个只包括<code>&#39;(&#39;，&#39;)&#39;，&#39;{&#39;，&#39;}&#39;，&#39;[&#39;，&#39;]&#39;</code>的字符串，判断字符串是否有效。</p>
<p>有效字符串需满足：</p>
<p>左括号必须用相同类型的右括号闭合。<br>左括号必须以正确的顺序闭合。<br><strong>注意空字符串可被认为是有效字符串。</strong></p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">示例 1:</span><br><span class="line"></span><br><span class="line">输入: <span class="string">"()"</span></span><br><span class="line">输出: <span class="literal">true</span></span><br><span class="line">示例 2:</span><br><span class="line"></span><br><span class="line">输入: <span class="string">"()[]&#123;&#125;"</span></span><br><span class="line">输出: <span class="literal">true</span></span><br><span class="line">示例 3:</span><br><span class="line"></span><br><span class="line">输入: <span class="string">"(]"</span></span><br><span class="line">输出: <span class="literal">false</span></span><br><span class="line">示例 4:</span><br><span class="line"></span><br><span class="line">输入: <span class="string">"([)]"</span></span><br><span class="line">输出: <span class="literal">false</span></span><br><span class="line">示例 5:</span><br><span class="line"></span><br><span class="line">输入: <span class="string">"&#123;[]&#125;"</span></span><br><span class="line">输出: <span class="literal">true</span></span><br></pre></td></tr></table></figure>



<p><strong>算法思路</strong></p>
<ul>
<li>栈的先入后出的特点和括号排序一致，即遇到左括号入栈，遇到右括号时将对应的栈顶元素左括号出栈，则遍历完所有括号之后<code>stack</code> 仍然为空。</li>
<li>建立哈希表存储所有左右括号的对应关系，（key 左括号， value 右括号）。这样查询2个括号是否对应只要O(1) 的时间复杂度；<ul>
<li>建立栈<code>stack</code> ，遍历字符串s并按照算法流程就行判断</li>
</ul>
</li>
</ul>
<p><strong>算法流程</strong></p>
<ul>
<li>如果c 是左括号，则入栈push<ul>
<li>否则通过哈希表来判断对应关系，若<code>stack</code> 栈顶出栈的括号<code>stack.pop()</code> 与当前括号c不对应，则提前返回false</li>
</ul>
</li>
</ul>
<p><strong>提前返回false</strong></p>
<ul>
<li><strong>提前返回优点：</strong> 在迭代过程中，提前发现不符合的括号并且返回，提升算法效率。<ul>
<li><strong>栈 stack 为空</strong> ： 此时 stack.pop()会报错，因此使用一个取巧的办法，<strong>给stack 赋一个初值 ？</strong> ， <strong>并在哈希表中建立 ？ 和 ？ 的对应关系。</strong>此时当<code>stack</code> 为空且<code>c</code> 是右括号的时候，可以正常提前返回false.</li>
<li><strong>字符串s 以左括号结尾：</strong> 这种情况下，可以正常的遍历完字符串，但是最后的左括号遗留了下来，这时候要判断最后栈的长度是不是等于1，如果等于，说明多出来一个左括号，不是有效的括号组合。</li>
</ul>
</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-195452276.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-195501520.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-195513439.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-195521791.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-195532859.png" alt="mark"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isValid</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// map来预存括号以及辅助判断字符</span></span><br><span class="line">        Map&lt;Character, Character&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">        map.put(<span class="string">'&#123;'</span>,<span class="string">'&#125;'</span>);</span><br><span class="line">        map.put(<span class="string">'['</span>,<span class="string">']'</span>);</span><br><span class="line">        map.put(<span class="string">'('</span>,<span class="string">')'</span>);</span><br><span class="line">        map.put(<span class="string">'?'</span>,<span class="string">'?'</span>);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 没有左括号直接返回false</span></span><br><span class="line">        <span class="keyword">if</span> (s.length() &gt; <span class="number">0</span> &amp;&amp; !map.containsKey(s.charAt(<span class="number">0</span>)))&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 栈</span></span><br><span class="line">        LinkedList&lt;Character&gt; list = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        list.add(<span class="string">'?'</span>);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 遍历字符串，检查括号符不符合要求</span></span><br><span class="line">        <span class="keyword">char</span>[] chars = s.toCharArray();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">char</span> c : chars) &#123;</span><br><span class="line">            <span class="comment">// 左括号放入栈中</span></span><br><span class="line">            <span class="keyword">if</span> (map.containsKey(c))&#123;</span><br><span class="line">                list.add(c);</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (map.get(list.removeLast()) != c)&#123;</span><br><span class="line">                <span class="comment">// 栈顶左括号和右括号是否匹配</span></span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 最后判断有没有遗留左括号</span></span><br><span class="line">        <span class="keyword">return</span> list.size() ==  <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<ul>
<li><strong>复杂度分析</strong><ul>
<li>时间复杂度 O(N)：正确的括号组合需要遍历 1 遍 <code>s</code>；</li>
<li>空间复杂度 O(N)：哈希表和栈使用线性的空间大小。</li>
</ul>
</li>
</ul>
<h3 id="2-1-4-739-每日温度"><a href="#2-1-4-739-每日温度" class="headerlink" title="2.1.4  739. 每日温度"></a>2.1.4  <a href="https://leetcode-cn.com/problems/daily-temperatures/" target="_blank" rel="noopener">739. 每日温度</a></h3><p><strong>题目描述：</strong></p>
<p><strong>本质</strong> ： 找到数组中第一个大于该元素数字的索引 ，并返回索引差值</p>
<p>根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。</p>
<p>例如，给定一个列表<code>temperatures = [73, 74, 75, 71, 69, 72, 76, 73]</code>，你的输出应该是 <code>[1, 1, 4, 2, 1, 1, 0, 0]</code>。</p>
<p>提示：气温 列表长度的范围是<code>[1, 30000]</code>。每个气温的值的均为华氏度，都是在<code>[30, 100]</code>范围内的整数。</p>
<p><strong>解法思路：单调递减栈</strong></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-205146576.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-205229904.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-205245835.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-205259273.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-205320457.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-205337913.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200726-205344516.png" alt="mark"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">int</span>[] dailyTemperatures(<span class="keyword">int</span>[] T) &#123;</span><br><span class="line">        <span class="comment">// 单调递减栈</span></span><br><span class="line">        Stack&lt;Integer&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        <span class="comment">// 结果集</span></span><br><span class="line">        <span class="keyword">int</span>[] ret = <span class="keyword">new</span> <span class="keyword">int</span>[T.length];</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; T.length; i++) &#123;</span><br><span class="line">            <span class="keyword">while</span> (!stack.isEmpty() &amp;&amp; T[i] &gt; T[stack.peek()]) &#123;</span><br><span class="line">                <span class="keyword">int</span> idx = stack.pop();</span><br><span class="line">                ret[idx] = i - idx;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 栈为空的话</span></span><br><span class="line">            stack.push(i);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ret;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>复杂度分析</strong></p>
<ul>
<li><strong>时间复杂度：O(n)，</strong>其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。</li>
<li><strong>空间复杂度：O(n)，</strong>其中 n是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。</li>
</ul>
<h3 id="2-1-5-150-逆波兰表达式求值"><a href="#2-1-5-150-逆波兰表达式求值" class="headerlink" title="2.1.5 150. 逆波兰表达式求值"></a>2.1.5 <a href="https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/" target="_blank" rel="noopener">150. 逆波兰表达式求值</a></h3><p><strong>题目描述</strong></p>
<p>根据<a href="https://baike.baidu.com/item/逆波兰式/128437" target="_blank" rel="noopener"> 逆波兰表示法</a>，求表达式的值。</p>
<p>有效的运算符包括 <code>+</code>, <code>-</code>, <code>*</code>, <code>/</code> 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。</p>
<p><strong>说明：</strong></p>
<ul>
<li>整数除法只保留整数部分。</li>
<li>给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">逆波兰表达式：</span><br><span class="line"></span><br><span class="line">逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。</span><br><span class="line"></span><br><span class="line">平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。</span><br><span class="line">该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。</span><br><span class="line">逆波兰表达式主要有以下两个优点：</span><br><span class="line"></span><br><span class="line">去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。</span><br><span class="line">适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。</span><br><span class="line"></span><br><span class="line">示例 1：</span><br><span class="line"></span><br><span class="line">输入: [&quot;2&quot;, &quot;1&quot;, &quot;+&quot;, &quot;3&quot;, &quot;*&quot;]</span><br><span class="line">输出: 9</span><br><span class="line">解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) &#x3D; 9</span><br><span class="line">示例 2：</span><br><span class="line"></span><br><span class="line">输入: [&quot;4&quot;, &quot;13&quot;, &quot;5&quot;, &quot;&#x2F;&quot;, &quot;+&quot;]</span><br><span class="line">输出: 6</span><br><span class="line">解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 &#x2F; 5)) &#x3D; 6</span><br><span class="line">示例 3：</span><br><span class="line"></span><br><span class="line">输入: [&quot;10&quot;, &quot;6&quot;, &quot;9&quot;, &quot;3&quot;, &quot;+&quot;, &quot;-11&quot;, &quot;*&quot;, &quot;&#x2F;&quot;, &quot;*&quot;, &quot;17&quot;, &quot;+&quot;, &quot;5&quot;, &quot;+&quot;]</span><br><span class="line">输出: 22</span><br><span class="line">解释: </span><br><span class="line">该算式转化为常见的中缀算术表达式为：</span><br><span class="line">  ((10 * (6 &#x2F; ((9 + 3) * -11))) + 17) + 5</span><br><span class="line">&#x3D; ((10 * (6 &#x2F; (12 * -11))) + 17) + 5</span><br><span class="line">&#x3D; ((10 * (6 &#x2F; -132)) + 17) + 5</span><br><span class="line">&#x3D; ((10 * 0) + 17) + 5</span><br><span class="line">&#x3D; (0 + 17) + 5</span><br><span class="line">&#x3D; 17 + 5</span><br><span class="line">&#x3D; 22</span><br></pre></td></tr></table></figure>



<p><strong>方法：单调栈</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">evalRPN</span><span class="params">(String[] tokens)</span> </span>&#123;</span><br><span class="line">        Stack&lt;Integer&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        <span class="comment">// 减少自动装箱拆箱的负担</span></span><br><span class="line">        Integer op1,op2;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 遍历字符串，进行运算</span></span><br><span class="line">        <span class="keyword">for</span> (String s : tokens) &#123;</span><br><span class="line">            <span class="keyword">switch</span> (s)&#123;</span><br><span class="line">                <span class="keyword">case</span> <span class="string">"+"</span> :</span><br><span class="line">                    op2 = stack.pop();</span><br><span class="line">                    op1 = stack.pop();</span><br><span class="line">                    stack.push(op1 + op2);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                <span class="keyword">case</span> <span class="string">"-"</span>:</span><br><span class="line">                    op2 = stack.pop();</span><br><span class="line">                    op1 = stack.pop();</span><br><span class="line">                    stack.push(op1 - op2);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                <span class="keyword">case</span> <span class="string">"*"</span>:</span><br><span class="line">                    op2 = stack.pop();</span><br><span class="line">                    op1 = stack.pop();</span><br><span class="line">                    stack.push(op1 * op2);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                <span class="keyword">case</span> <span class="string">"/"</span>:</span><br><span class="line">                    op2 = stack.pop();</span><br><span class="line">                    op1 = stack.pop();</span><br><span class="line">                    stack.push(op1 / op2);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                <span class="keyword">default</span>:</span><br><span class="line">                    stack.push(Integer.valueOf(s));</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 返回最后栈顶元素</span></span><br><span class="line">        <span class="keyword">return</span> stack.pop();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>







<h1 id="2-队列和BFS"><a href="#2-队列和BFS" class="headerlink" title="2. 队列和BFS"></a>2. 队列和BFS</h1><h2 id="2-1-BFS"><a href="#2-1-BFS" class="headerlink" title="2.1 BFS"></a>2.1 BFS</h2><ul>
<li><p>广度优先搜索（BFS）是一个常见应用是从根节点到目标节点的最短路径。</p>
</li>
<li><p>在本文中，我们提供了一个示例来解释在 BFS 算法中是如何逐步应用队列的。</p>
</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200720/162240980.gif" alt="mark"></p>
<p><strong>分析</strong></p>
<ol>
<li>节点的处理顺序是什么？</li>
</ol>
<ul>
<li>在第一轮中，我们处理根节点。</li>
<li>在第二轮中，我们处理第二层节点。</li>
<li>第三轮中，我们处理第三层节点。</li>
<li>。。。。</li>
</ul>
<ul>
<li>与树的<strong>层序遍历</strong>类似，<code>越是接近根结点的结点将越早地遍历</code>。</li>
</ul>
<ol start="2">
<li>队列的入队和出队顺序是什么？</li>
</ol>
<ul>
<li>首先将根节点入队，逐个处理已经在队列中的节点，并将所有的邻居添加到队列中。值得注意的是，新添加的节点并不会立即遍历，而是在下一轮搜索中处理。</li>
<li>节点处理的顺序和添加到队列的顺序是完全相同的，即先进先出（FIFO）,这就是我们为什么使用队列的原因。</li>
</ul>
<h2 id="2-2-BFS两种模板"><a href="#2-2-BFS两种模板" class="headerlink" title="2.2 BFS两种模板"></a>2.2 BFS两种模板</h2><ul>
<li>之前，我们已经介绍了使用 BFS 的两个主要方案：<code>遍历</code>或<code>找出最短路径</code>。通常，这发生在树或图中。正如我们在章节描述中提到的，BFS 也可以用于更抽象的场景中。</li>
</ul>
<p><strong>模板一：</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Return the length of the shortest path between root and target node.</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">BFS</span><span class="params">(Node root, Node target)</span> </span>&#123;</span><br><span class="line">    Queue&lt;Node&gt; queue;  <span class="comment">// store all nodes which are waiting to be processed</span></span><br><span class="line">    <span class="keyword">int</span> step = <span class="number">0</span>;       <span class="comment">// number of steps neeeded from root to current node</span></span><br><span class="line">    <span class="comment">// initialize</span></span><br><span class="line">    add root to queue;</span><br><span class="line">    <span class="comment">// BFS</span></span><br><span class="line">    <span class="keyword">while</span> (queue is not empty) &#123;</span><br><span class="line">        step = step + <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// iterate the nodes which are already in the queue</span></span><br><span class="line">        <span class="keyword">int</span> size = queue.size();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; size; ++i) &#123;</span><br><span class="line">            Node cur = the first node in queue;</span><br><span class="line">            <span class="keyword">return</span> step <span class="keyword">if</span> cur is target;</span><br><span class="line">            <span class="keyword">for</span> (Node next : the neighbors of cur) &#123;</span><br><span class="line">                add next to queue;</span><br><span class="line">            &#125;</span><br><span class="line">            remove the first node from queue;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;          <span class="comment">// there is no path from root to target</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>每一轮中，<strong>队列的节点是等待处理的节点</strong></li>
<li>在每个更外的一层<code>while</code> 循环之后，我们举例根节点更远一步。变量<code>step</code> 从根节点到我们正在访问的节点的距离。</li>
</ul>
<p><strong>模板二</strong></p>
<ul>
<li>有时候，确保我们永远不会访问同一个节点两次很重要。</li>
<li>否则的话，我们可能会陷入无限死循环，如果是这样，我们可以添加一个哈希set来解决这样的问题，下面是修改后的伪代码：</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 计算从起点 start 到终点 target 的最近距离</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">BFS</span><span class="params">(Node start, Node target)</span> </span>&#123;</span><br><span class="line">    Queue&lt;Node&gt; q; <span class="comment">// 核心数据结构</span></span><br><span class="line">    Set&lt;Node&gt; visited; <span class="comment">// 避免走回头路</span></span><br><span class="line">    </span><br><span class="line">    q.offer(start); <span class="comment">// 将起点加入队列</span></span><br><span class="line">    visited.add(start);</span><br><span class="line">    <span class="keyword">int</span> step = <span class="number">0</span>; <span class="comment">// 记录扩散的步数</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (q not empty) &#123;</span><br><span class="line">        <span class="keyword">int</span> sz = q.size();</span><br><span class="line">        <span class="comment">/* 将当前队列中的所有节点向四周扩散 */</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; sz; i++) &#123;</span><br><span class="line">            Node cur = q.poll();</span><br><span class="line">            <span class="comment">/* 划重点：这里判断是否到达终点 */</span></span><br><span class="line">            <span class="keyword">if</span> (cur is target)</span><br><span class="line">                <span class="keyword">return</span> step;</span><br><span class="line">            <span class="comment">/* 将 cur 的相邻节点加入队列 */</span></span><br><span class="line">            <span class="keyword">for</span> (Node x : cur.adj())</span><br><span class="line">                <span class="keyword">if</span> (x not in visited) &#123;</span><br><span class="line">                    q.offer(x);</span><br><span class="line">                    visited.add(x);</span><br><span class="line">                &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">/* 划重点：更新步数在这里 */</span></span><br><span class="line">        step++;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<ul>
<li><strong>队列q 就不用说了，BFS核心的数据结构；</strong></li>
<li><code>cur.adj()</code> 表示 <code>cur</code> 相邻的节点，比如说二维数组中，<code>cur</code> 的上下左右位置就是相邻的节点；</li>
<li><code>visited()</code> 节点的作用就是防止走回头路<ul>
<li><strong>大部分情况下，<code>visited</code> 数组或者说 哈希表 是必须的</strong></li>
<li><strong>但是像二叉树一般的结构，没有子节点到父节点的指针，不会走回头路就不需要<code>visited</code></strong></li>
</ul>
</li>
</ul>
<h2 id="2-3-BFS-题目1：-102-二叉树的层序遍历"><a href="#2-3-BFS-题目1：-102-二叉树的层序遍历" class="headerlink" title="2.3 BFS 题目1： 102. 二叉树的层序遍历"></a>2.3 BFS 题目1： <a href="https://leetcode-cn.com/problems/binary-tree-level-order-traversal/" target="_blank" rel="noopener">102. 二叉树的层序遍历</a></h2><p>给你一个二叉树，请你返回其按 <strong>层序遍历</strong> 得到的节点值。 （即逐层地，从左到右访问所有节点）。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">示例：</span><br><span class="line">二叉树：[3,9,20,null,null,15,7],</span><br><span class="line"></span><br><span class="line">    3</span><br><span class="line">   &#x2F; \</span><br><span class="line">  9  20</span><br><span class="line">    &#x2F;  \</span><br><span class="line">   15   7</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[</span><br><span class="line">  [3],</span><br><span class="line">  [9,20],</span><br><span class="line">  [15,7]</span><br><span class="line">]</span><br></pre></td></tr></table></figure>



<p><strong>思路：BFS</strong></p>
<p>给定一个二叉树，返回其按层序遍历得到的节点值。 层序遍历即逐层地、从左到右访问所有结点。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span></span>&#123;</span><br><span class="line">    <span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; levelOrder(TreeNode root)&#123;</span><br><span class="line">        <span class="comment">// res 记录最后结果</span></span><br><span class="line">        List&lt;List&lt;Integer&gt;&gt; result = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 特判</span></span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> result;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 队列（LinkedList实现）</span></span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 根节点放入队列</span></span><br><span class="line">        queue.add(root);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">            List&lt;Integer&gt; subList = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line"></span><br><span class="line">            <span class="keyword">int</span> curSize = queue.size();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; curSize; i++) &#123;</span><br><span class="line">                <span class="comment">// 取出队列首元素并删除</span></span><br><span class="line">                TreeNode curr = queue.poll();</span><br><span class="line">                <span class="keyword">if</span> (curr != <span class="keyword">null</span>)&#123;</span><br><span class="line">                    <span class="comment">// 队首元素放到结果中</span></span><br><span class="line">                    subList.add(curr.val);</span><br><span class="line">                    <span class="comment">// 对子节点进行处理</span></span><br><span class="line">                    <span class="keyword">if</span> (curr.left != <span class="keyword">null</span>)&#123;</span><br><span class="line">                        queue.add(curr.left);</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (curr.right != <span class="keyword">null</span>)&#123;</span><br><span class="line">                        queue.add(curr.right);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            result.add(subList);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200809-163226648.gif" alt="mark"></p>
<ul>
<li>可以看到，在 while 循环的每一轮中，都是将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历。</li>
</ul>
<p><strong>复杂度分析</strong></p>
<p>记树上所有节点的个数为 nn。</p>
<ul>
<li>时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。</li>
<li>空间复杂度：队列中元素的个数不超过 nn 个，故渐进空间复杂度为 O(n)。</li>
</ul>
<h2 id="2-4-BFS-题目2：111-二叉树的最小深度"><a href="#2-4-BFS-题目2：111-二叉树的最小深度" class="headerlink" title="2.4 BFS 题目2：111. 二叉树的最小深度"></a>2.4 BFS 题目2：<a href="https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/" target="_blank" rel="noopener">111. 二叉树的最小深度</a></h2><p><strong>题目描述</strong></p>
<p>给定一个二叉树，找出其最小深度。</p>
<p>最小深度是从根节点到最近叶子节点的最短路径上的节点数量。</p>
<p><strong>说明:</strong> 叶子节点是指没有子节点的节点。</p>
<p><strong>示例:</strong></p>
<p>给定二叉树 <code>[3,9,20,null,null,15,7]</code>,</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">  3</span><br><span class="line"> &#x2F; \</span><br><span class="line">9  20</span><br><span class="line">  &#x2F;  \</span><br><span class="line"> 15   7</span><br></pre></td></tr></table></figure>





<p><strong>思路：BFS</strong></p>
<ul>
<li>首先来看看DFS和BFS的区别</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-150819598.gif" alt="mark"></p>
<ul>
<li><p>这个遍历顺序也是 BFS 能够用来解「层序遍历」、「最短路径」问题的根本原因。</p>
</li>
<li></li>
</ul>
<h2 id="2-5-BFS-题目3-：-279-完全平方数"><a href="#2-5-BFS-题目3-：-279-完全平方数" class="headerlink" title="2.5 BFS  题目3 ： 279-完全平方数"></a>2.5 BFS  题目3 ： 279-<a href="https://leetcode-cn.com/problems/perfect-squares/" target="_blank" rel="noopener">完全平方数</a></h2><p>给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">示例 <span class="number">1</span>:</span><br><span class="line"></span><br><span class="line">输入: n = <span class="number">12</span></span><br><span class="line">输出: <span class="number">3</span> </span><br><span class="line">解释: <span class="number">12</span> = <span class="number">4</span> + <span class="number">4</span> + <span class="number">4</span>.</span><br><span class="line">示例 <span class="number">2</span>:</span><br><span class="line"></span><br><span class="line">输入: n = <span class="number">13</span></span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line">解释: <span class="number">13</span> = <span class="number">4</span> + <span class="number">9</span>.</span><br></pre></td></tr></table></figure>





<p><strong>解法：BFS（下面一图胜千言）</strong></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200809-170946859.png" alt="mark"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numSquares</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">        Queue&lt;Integer&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        HashSet&lt;Integer&gt; visited = <span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">        <span class="keyword">int</span> level = <span class="number">0</span>;</span><br><span class="line">        queue.add(n);</span><br><span class="line">        <span class="keyword">while</span> (!queue.isEmpty()) &#123;</span><br><span class="line">            <span class="keyword">int</span> size = queue.size();</span><br><span class="line">            level++; <span class="comment">// 开始生成下一层</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">                <span class="keyword">int</span> cur = queue.poll();</span><br><span class="line">                <span class="comment">//依次减 1, 4, 9... 生成下一层的节点</span></span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j * j &lt;= cur; j++) &#123;</span><br><span class="line">                    <span class="keyword">int</span> next = cur - j * j;</span><br><span class="line">                    <span class="keyword">if</span> (next == <span class="number">0</span>) &#123;</span><br><span class="line">                        <span class="keyword">return</span> level;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (!visited.contains(next)) &#123;</span><br><span class="line">                        queue.offer(next);</span><br><span class="line">                        visited.add(next);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>









<h1 id="3-栈和DFS"><a href="#3-栈和DFS" class="headerlink" title="3. 栈和DFS"></a>3. 栈和DFS</h1><ul>
<li><p>正如我们在本章的描述中提到的，在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序。</p>
</li>
<li><p>与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。</p>
</li>
<li><p>在本文中，我们将为你提供一个 DFS 的递归模板，并向你展示栈是如何帮助这个过程的。</p>
</li>
</ul>
<p><strong>模板</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;*</span><br><span class="line"> * Return true if there is a path from cur to target.</span><br><span class="line"> *&#x2F;</span><br><span class="line">boolean DFS(Node cur, Node target, Set&lt;Node&gt; visited) &#123;</span><br><span class="line">    return true if cur is target;</span><br><span class="line">    for (next : each neighbor of cur) &#123;</span><br><span class="line">        if (next is not in visited) &#123;</span><br><span class="line">            add next to visted;</span><br><span class="line">            return true if DFS(next, target, visited) &#x3D;&#x3D; true;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return false;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="3-1-94-二叉树的中序遍历"><a href="#3-1-94-二叉树的中序遍历" class="headerlink" title="3.1 94. 二叉树的中序遍历"></a>3.1 <a href="https://leetcode-cn.com/problems/binary-tree-inorder-traversal/" target="_blank" rel="noopener">94. 二叉树的中序遍历</a></h2><p>给定一根二叉树，返回它的中序遍历</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">Input: [1,null,2,3]</span><br><span class="line">   1</span><br><span class="line">    \</span><br><span class="line">     2</span><br><span class="line">    &#x2F;</span><br><span class="line">   3</span><br><span class="line"></span><br><span class="line">Output: [1,3,2]</span><br></pre></td></tr></table></figure>



<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">inorderTraversal</span><span class="params">(TreeNode root)</span></span>&#123;</span><br><span class="line">        List&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        helper(root,res);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">helper</span><span class="params">(TreeNode root, List&lt;Integer&gt; res)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 判断当前是否是null</span></span><br><span class="line">        <span class="keyword">if</span> (root != <span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="comment">// 1. 左子树</span></span><br><span class="line">            <span class="keyword">if</span> (root.left != <span class="keyword">null</span>)&#123;</span><br><span class="line">                helper(root.left,res);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 2. 打印</span></span><br><span class="line">            res.add(root.val);</span><br><span class="line">            <span class="comment">// 3. 右子树</span></span><br><span class="line">            <span class="keyword">if</span> (root.right != <span class="keyword">null</span>)&#123;</span><br><span class="line">                helper(root.right,res);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>前序遍历：</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">preorderTraversal</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        List&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        DFS(root,res);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">DFS</span><span class="params">(TreeNode root,List&lt;Integer&gt; res)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(root != <span class="keyword">null</span>)&#123;</span><br><span class="line">            res.add(root.val);</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span>(root.left != <span class="keyword">null</span>)&#123;DFS(root.left,res);&#125;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span>(root.right != <span class="keyword">null</span>)&#123;DFS(root.right,res);&#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>后序遍历</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for a binary tree node.</span></span><br><span class="line"><span class="comment"> * public class TreeNode &#123;</span></span><br><span class="line"><span class="comment"> *     int val;</span></span><br><span class="line"><span class="comment"> *     TreeNode left;</span></span><br><span class="line"><span class="comment"> *     TreeNode right;</span></span><br><span class="line"><span class="comment"> *     TreeNode(int x) &#123; val = x; &#125;</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">postorderTraversal</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        List&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        DFS(root,res);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">DFS</span><span class="params">(TreeNode root,List&lt;Integer&gt; res)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(root != <span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(root.left != <span class="keyword">null</span>)&#123;DFS(root.left,res);&#125;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span>(root.right != <span class="keyword">null</span>)&#123;DFS(root.right,res);&#125;</span><br><span class="line"></span><br><span class="line">            res.add(root.val);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>









<h2 id="3-3-329-矩阵中的最长递增路径"><a href="#3-3-329-矩阵中的最长递增路径" class="headerlink" title="3.3 329. 矩阵中的最长递增路径"></a>3.3 <a href="https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/" target="_blank" rel="noopener">329. 矩阵中的最长递增路径</a></h2>
      
      <!-- reward -->
      
      <div id="reward-btn">
        打赏
      </div>
      
    </div>
      <!-- copyright -->
      
        <div class="declare">
          <ul class="post-copyright">
            <li>
              <i class="ri-copyright-line"></i>
              <strong>版权声明： </strong s>
              本博客所有文章除特别声明外，均采用 <a href="https://www.apache.org/licenses/LICENSE-2.0.html" rel="external nofollow"
                target="_blank">Apache License 2.0</a> 许可协议。转载请注明出处！
            </li>
          </ul>
        </div>
        
    <footer class="article-footer">
      
          
<div class="share-btn">
      <span class="share-sns share-outer">
        <i class="ri-share-forward-line"></i>
        分享
      </span>
      <div class="share-wrap">
        <i class="arrow"></i>
        <div class="share-icons">
          
          <a class="weibo share-sns" href="javascript:;" data-type="weibo">
            <i class="ri-weibo-fill"></i>
          </a>
          <a class="weixin share-sns wxFab" href="javascript:;" data-type="weixin">
            <i class="ri-wechat-fill"></i>
          </a>
          <a class="qq share-sns" href="javascript:;" data-type="qq">
            <i class="ri-qq-fill"></i>
          </a>
          <a class="douban share-sns" href="javascript:;" data-type="douban">
            <i class="ri-douban-line"></i>
          </a>
          <!-- <a class="qzone share-sns" href="javascript:;" data-type="qzone">
            <i class="icon icon-qzone"></i>
          </a> -->
          
          <a class="facebook share-sns" href="javascript:;" data-type="facebook">
            <i class="ri-facebook-circle-fill"></i>
          </a>
          <a class="twitter share-sns" href="javascript:;" data-type="twitter">
            <i class="ri-twitter-fill"></i>
          </a>
          <a class="google share-sns" href="javascript:;" data-type="google">
            <i class="ri-google-fill"></i>
          </a>
        </div>
      </div>
</div>

<div class="wx-share-modal">
    <a class="modal-close" href="javascript:;"><i class="ri-close-circle-line"></i></a>
    <p>扫一扫，分享到微信</p>
    <div class="wx-qrcode">
      <img src="//api.qrserver.com/v1/create-qr-code/?size=150x150&data=http://zhuuu.work/2020/07/20/LeetcodeExplore/%E9%98%9F%E5%88%97%E5%92%8C%E6%A0%88-%E5%90%88%E9%9B%86/" alt="微信分享二维码">
    </div>
</div>

<div id="share-mask"></div>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Leetcode/" rel="tag">Leetcode</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%A0%88/" rel="tag">栈</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E9%98%9F%E5%88%97/" rel="tag">队列</a></li></ul>


    </footer>

  </div>

  
  
  <nav class="article-nav">
    
      <a href="/2020/07/20/LeetcodeExplore/%E5%90%84%E7%A7%8D%E5%8F%8D%E8%BD%AC-%E5%90%88%E9%9B%86/" class="article-nav-link">
        <strong class="article-nav-caption">上一篇</strong>
        <div class="article-nav-title">
          
            各种反转-合集
          
        </div>
      </a>
    
    
      <a href="/2020/07/17/assembly/%E6%B1%87%E7%BC%96-07-%E5%86%85%E5%AD%98/" class="article-nav-link">
        <strong class="article-nav-caption">下一篇</strong>
        <div class="article-nav-title">汇编-07-内存</div>
      </a>
    
  </nav>


  

  
  
<!-- valine评论 -->
<div id="vcomments-box">
    <div id="vcomments">
    </div>
</div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='https://cdn.jsdelivr.net/npm/valine@1.3.10/dist/Valine.min.js'></script>
<script>
    new Valine({
        el: '#vcomments',
        notify: false,
        verify: '',
        app_id: '',
        app_key: '',
        path: window.location.pathname,
        avatar: 'mp',
        placeholder: '给我的文章加点评论吧~',
        recordIP: true
    });
    const infoEle = document.querySelector('#vcomments .info');
    if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
        infoEle.childNodes.forEach(function (item) {
            item.parentNode.removeChild(item);
        });
    }
</script>
<style>
    #vcomments-box {
        padding: 5px 30px;
    }

    @media screen and (max-width: 800px) {
        #vcomments-box {
            padding: 5px 0px;
        }
    }

    #vcomments-box #vcomments {
        background-color: #fff;
    }

    .v .vlist .vcard .vh {
        padding-right: 20px;
    }

    .v .vlist .vcard {
        padding-left: 10px;
    }
</style>

  

  
  
<div class="gitalk" id="gitalk-container"></div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.css">


<script src="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.min.js"></script>


<script src="https://cdn.jsdelivr.net/npm/blueimp-md5@2.10.0/js/md5.min.js"></script>

<script type="text/javascript">
  var gitalk = new Gitalk({
    clientID: 'db188ed8c86dc4b0dbf3',
    clientSecret: 'a58f92160e5a9efd726b7d533000a0737f3e3f3e',
    repo: 'Blog-comments',
    owner: 'Zhuuuuuuuu',
    admin: ['Zhuuuuuuuu'],
    // id: location.pathname,      // Ensure uniqueness and length less than 50
    id: md5(location.pathname),
    distractionFreeMode: false,  // Facebook-like distraction free mode
    pagerDirection: 'last'
  })

  gitalk.render('gitalk-container')
</script>

  

</article>
</section>
      <footer class="footer">
  <div class="outer">
    <ul class="list-inline">
      <li>
        &copy;
        2019-2021
        Zhuuu
      </li>
      <li>
        
      </li>
    </ul>
    <ul class="list-inline">
      <li>
        
        
        <span>
  <i>PV:<span id="busuanzi_value_page_pv"></span></i>
  <i>UV:<span id="busuanzi_value_site_uv"></span></i>
</span>
        
      </li>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s9.cnzz.com/z_stat.php?id=1278069914&amp;web_id=1278069914'></script>
        
      </li>
    </ul>
  </div>
</footer>
    <div class="to_top">
        <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>
      </div>
    </main>
      <aside class="sidebar">
        <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="朱酱酱的学习博客"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">主页</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">标签</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/JVM/">JVM</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/JDK%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/">JDK源码</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/">多线程</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Mysql/">Mysql</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Redis/">Redis</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E8%AE%BE%E8%AE%A1%E8%80%85%E6%A8%A1%E5%BC%8F/">设计模式</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/MyBatis/">MyBatis</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/SpringMVC/">SpringMVC</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Spring/">Spring</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/SpringBoot/">SpringBoot</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/">Linux</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Leetcode/">Leetcode</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E5%89%8D%E7%AB%AF/">前端</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E7%BD%91%E7%BB%9C%E7%BC%96%E7%A8%8B/">网络编程</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/photoshop/">photoshop</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="http://smartzhuuu.lofter.com/" target="_blank" rel="noopener">摄影</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2020/about">关于我</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="Search">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
      </aside>
      <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯咖啡吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
      
<script src="/js/jquery-2.0.3.min.js"></script>


<script src="/js/jquery.justifiedGallery.min.js"></script>


<script src="/js/lazyload.min.js"></script>


<script src="/js/busuanzi-2.3.pure.min.js"></script>


<script src="/js/share.js"></script>



<script src="/fancybox/jquery.fancybox.min.js"></script>




<script>
  try {
    var typed = new Typed("#subtitle", {
    strings: ['昨夜西风凋碧树。独上高楼，望尽天涯路','衣带渐宽终不悔，为伊消得人憔悴。','众里寻他千百度。蓦然回首，那人却在，灯火阑珊处。'],
    startDelay: 0,
    typeSpeed: 200,
    loop: true,
    backSpeed: 100,
    showCursor: true
    });
  } catch (err) {
  }
  
</script>




<script src="/js/tocbot.min.js"></script>

<script>
  // Tocbot_v4.7.0  http://tscanlin.github.io/tocbot/
  tocbot.init({
    tocSelector: '.tocbot',
    contentSelector: '.article-entry',
    headingSelector: 'h1, h2, h3, h4, h5, h6',
    hasInnerContainers: true,
    scrollSmooth: true,
    scrollContainer:'main',
    positionFixedSelector: '.tocbot',
    positionFixedClass: 'is-position-fixed',
    fixedSidebarOffset: 'auto',
    onClick: (e) => {
      $('.toc-link').removeClass('is-active-link');
      $(`a[href=${e.target.hash}]`).addClass('is-active-link');
      $(e.target.hash).scrollIntoView();
      return false;
    }
  });
</script>


<script>
  var ayerConfig = {
    mathjax: true
  }
</script>


<script src="/js/ayer.js"></script>


<script src="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.css">


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css">
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script>



<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
      tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
  });

  MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for(i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.6/unpacked/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>


<script type="text/javascript" src="https://js.users.51.la/20544303.js"></script>
  </div>
</body>

</html>